/**
 * @file 013.二维子矩阵的和.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-12-09
 *
 * @copyright Copyright (c) 2021
 *
 * 303.区域和检索——数组不可变
 * 304.二维区域和检索——矩阵不可变
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 303.
class NumArray
{
public:
    NumArray(vector<int> &nums)
    {
        int n = nums.size();
        _preSum.reserve(n + 1);
        _preSum[0] = 0;
        for (int i = 0; i < n; ++i) {
            _preSum[i + 1] = _preSum[i] + nums[i];
        }
    }

    int sumRange(int left, int right)
    {
        return _preSum[right + 1] - _preSum[left];
    }

private:
    vector<int> _preSum;
};

// 304.一维前缀和
class NumMatrix1
{
public:
    NumMatrix1(vector<vector<int>> &matrix)
    {
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; ++i) {
            vector<int> preSum(n + 1, 0);
            for (int j = 0; j < n; ++j) {
                preSum[j + 1] = preSum[j] + matrix[i][j];
            }
            _d1PreSum.push_back(preSum); // m行n+1列
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2)
    { // O(row2-row1)
        int sum = 0;
        for (int i = row1; i <= row2; ++i) {
            sum += _d1PreSum[i][col2 + 1] - _d1PreSum[i][col1];
        }
        return sum;
    }

private:
    vector<vector<int>> _d1PreSum; // 一维前缀和
};

// 304.二维前缀和
class NumMatrix
{
public:
    NumMatrix(vector<vector<int>> &matrix)
    {
        // 二维前缀和：dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+matrix[i][j]
        int m = matrix.size(), n = matrix[0].size();
        if (m > 0) {
            _d2PreSum.resize(m + 1, vector<int>(n + 1));
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    _d2PreSum[i + 1][j + 1] = _d2PreSum[i][j + 1] + _d2PreSum[i + 1][j] - _d2PreSum[i][j] + matrix[i][j];
                }
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2)
    {
        return _d2PreSum[row2 + 1][col2 + 1] - _d2PreSum[row1][col2 + 1] - _d2PreSum[row2 + 1][col1] + _d2PreSum[row1][col1];
    }

private:
    vector<vector<int>> _d2PreSum;
};

int main()
{
    vector<int> nums;
    nums.reserve(20);
    cout << nums.size() << endl;
    cout << nums.capacity() << endl;
    return 0;
}